#include <bits/stdc++.h>
using namespace std;
// int main()
// {
//     string s,s1;cin>>s;
//     char ch=s.back();
//     int back=ch-'0';
//     for(int i=0;i<s.size();i++)
//     {
//         if(s[i]=='-')continue;
//         s1+=s[i];
//     }
//     long long sum=0;
//     for(int i=0;i<s1.size()-1;i++)sum+=((s1[i]-'0')*(i+1));
//     sum%=11;
//     if((sum==10&&ch=='X')||sum==back)cout<<"Right"<<endl;
//     else
//     {
//         if(sum==10)s.back()='X';
//         else s.back()=sum+'0';
//         cout<<s<<endl;
//     }
//     return 0;
// }

// int n, m;
// int dx[4] = {0, 0, 1, -1};
// int dy[4] = {1, -1, 0, 0};
// int enSelectdestcount; // 出口的数量
// int minlen = INT_MAX;
// void bfs(vector<vector<char>> &ret, int i, int j)
// {
//     //存储点的信息
//     queue<pair<int, int>> q;
//     q.push({i, j});

//     //存储的是起点到每个点的距离
//     vector<vector<int>> dist(n + 1, vector<int>(m + 1, -1));
//     dist[i][j] = 0;
//     //队列为空说明遍历完整个迷宫了或者这个点四周都是墙壁，不能找到出口了
//     while (!q.empty())
//     {
//         // 取出队头元素
//         auto [x, y] = q.front();
//         q.pop();

//         for (int k = 0; k < 4; k++)
//         {
//             int nx = x + dx[k], ny = y + dy[k];

//             //这个点是否访问过以及它是否可以访问
//             if (nx < 1 || nx > n || ny < 1 || ny > m || ret[nx][ny] == '*' || dist[nx][ny] != -1)
//                 continue;

//             dist[nx][ny] = dist[x][y] + 1;
//             if (ret[nx][ny] == 'e')
//             {
//                 enSelectdestcount++;
//                 minlen = min(minlen, dist[nx][ny]);
//             }
//             if (ret[nx][ny] == '.')
//                 q.push({nx, ny});
//         }
//     }
// }
// int main()
// {
//     cin >> n >> m;
//     vector<vector<char>> ret(n + 1, vector<char>(m + 1, 0));
//     int tempi = -1, tempj = -1;
//     bool found = false;
//     for (int i = 1; i <= n; i++)
//         for (int j = 1; j <= m; j++)
//         {
//             cin >> ret[i][j];
//             if (ret[i][j] == 'k')
//             {
//                 found = true;
//                 tempi = i;
//                 tempj = j;
//             }
//         }
//     bfs(ret, tempi, tempj);
//     if (found == false || enSelectdestcount == 0)
//         cout << -1 << endl;
//     else
//         cout << enSelectdestcount << " " << minlen << endl;
//     return 0;
// }

//记忆化搜素
class Solution {
    public:
        int n,m;
        int dx[4]={0,0,1,-1};
        int dy[4]={1,-1,0,0};
        int count=0;
        int dfs(vector<vector<int> >& matrix,vector<vector<int> >& mem,int i,int j)
        {
            if(mem[i][j]!=-1)return mem[i][j];
            int maxlen=1;
            for(int k=0;k<4;k++)
            {
                int x=i+dx[k],y=j+dy[k];
                if(x>=0&&x<n&&y>=0&&y<=m&&matrix[x][y]>matrix[i][j])
                {
                    maxlen=max(maxlen,1+dfs(matrix,mem,x,y));
                }
            }
            mem[i][j]=maxlen;
            return maxlen;
        }
        int solve(vector<vector<int> >& matrix) {
            n=matrix.size();m=matrix[0].size();
            vector<vector<int>> mem(n,vector<int>(m,-1));
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    count=max(count,dfs(matrix,mem,i,j));
                }
            }
            return count;
        }
    };